package algorithm.dac;

/**
 * 分治算法  其实就是把复杂问题简单化
 * 比如汉罗塔问题
 * 1、如果只有一个盘子则  a --> c
 * 2、如果有>=2个盘子
 *      则 分成两份 上面一份,最后一个一份
 *      上面那份 a --> b
 *      最后一个 a --> c
 *      b中的盘子  b --> c
 */
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(10, "A", "B", "C");
        System.out.println("count --> " + count);
    }

    private static int count = 0;
    private static void hanoiTower(int num, String a, String b, String c) {
        count++;
        if (num == 1) {
            System.out.println(num + " -- > " + a + " --> " + c);
            return;
        }
        // 盘子数量大于等于2个 则 从a到b   最后一个盘子 a到c  其余的盘子 b到c
        // n-1 个盘子 从a 到 b
        hanoiTower(num - 1, a, c, b);
        // 最后一个盘子 a --> c
        System.out.println(num + " -- > " + a + " --> " + c);
        // 其余盘子 b -- c
        hanoiTower(num - 1, b, a, c);

    }
}
